package com.gitee.feizns.explore.data_structure.tree.bs.easy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

/**
 * @author feizns
 * @since 2019/12/9
 */
public class LevelOrderTraversal {

    public static List<List<Integer>> levelOrder(TreeNode root) {
        Map<TreeNode, Integer> nodeLevel = new HashMap<>();
        List<List<Integer>> lists = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if ( root != null ) {
            queue.add(root);
            nodeLevel.put(root, 0);
        }
        while ( !queue.isEmpty() ) {
            TreeNode node = queue.remove();
            Integer level = nodeLevel.get(node);

            if ( level < lists.size() )
                lists.get(level).add(node.val);
            else
                lists.add(new ArrayList<>(Arrays.asList(node.val)));

            if ( node.left != null ) {
                queue.add(node.left);
                nodeLevel.put(node.left, level + 1);
            }
            if ( node.right != null ) {
                queue.add(node.right);
                nodeLevel.put(node.right, level + 1);
            }
        }
        return lists;
    }

//    public static List<List<Integer>> LevelOrder(TreeNode root) {
//        List<List<TreeNode>> list = new ArrayList<>();
//        if ( root != null )
//            list.add(Arrays.asList(root));
//        return LevelOrder(list).stream().map(l -> l.stream().map(TreeNode::getVal).collect(Collectors.toList())).collect(Collectors.toList());
//    }
//
//    private static List<List<TreeNode>> LevelOrder(List<List<TreeNode>> lists) {
//        if ( !lists.isEmpty() ) {
//            List<TreeNode> lastLevel = lists.get(lists.size() - 1);
//            List<TreeNode> newLevel = new LinkedList<>();
//            for (TreeNode node : lastLevel) {
//                if ( node.left != null )
//                    newLevel.add(node.left);
//                if ( node.right != null )
//                    newLevel.add(node.right);
//            }
//
//            if ( !newLevel.isEmpty() ) {
//                lists.add(newLevel);
//                LevelOrder(lists);
//            }
//        }
//        return lists;
//    }

    public static void main(String[] args) {
        System.out.println(levelOrder(create()));
    }

    private static TreeNode create() {
        TreeNode ret = new TreeNode(10);
        ret.left = new TreeNode(9);
        ret.right = new TreeNode(20);
        ret.right.left = new TreeNode(15);
        ret.right.right = new TreeNode(7);
        return ret;
    }

}
